package formal.tree.ergodic;

import java.util.*;

/**
 * 二叉树的前序遍历-要求非递归
 *
 * @author DengYuan2
 * @create 2021-01-19 21:43
 */
public class M_144 {
    public static void main(String[] args) {
//        Integer[] a = {1,null,2};
        Integer[] a = {1, 2, 3, 4, 5, 6, 7};
        TreeNode treeNode = TreeNode.generateTree(a);
        List<Integer> res = preorderTraversal2(treeNode);
        for (Integer i : res) {
            System.out.println(i);
        }
    }

    /**
     * 我的写法-很慢
     * 思路：左节点放进队列，直到队列里没有东西，右节点放入栈，队列没有东西时则从栈中取出放入
     *
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return resList;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                resList.add(poll.val);
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    stack.push(poll.right);
                }
            }
            if (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                queue.offer(pop);
            }
        }
        return resList;
    }

    /**
     * 大神的写法-直接用栈
     * @param root
     * @return
     */
    public static List<Integer> preorderTraversal2(TreeNode root) {
        ArrayList<Integer> resList = new ArrayList<>();
        if (root == null) {
            return resList;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            resList.add(pop.val);
            if (pop.right!=null){
                stack.push(pop.right);
            }
            if (pop.left!=null){
                stack.push(pop.left);
            }
        }
        return resList;
    }
}
